package day36_837;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/14 19:57
 * @Version 1.0
 */
public class Solution {
    public double new21Game(int n, int k, int maxPts) {
        //初始化动态规划数组长度为 k + maxPts
        double[] dp = new double[k + maxPts];
        double res = 0;

        //根据推导可知，当 k <= x <= n 时, 爱丽丝获胜; x > n 时, 爱丽丝失败
        for (int i = k; i < k + maxPts; i++) {
            if (i > n) {
                dp[i] = 0;
            } else {
                dp[i] = 1;
            }
            res += dp[i];
        }

        //从 k - 1 往前遍历
        for (int i = k - 1; i >= 0; i--) {
            dp[i] = res / maxPts;
            //窗口滑动（向左滑动）, 每次滑动减去最右边一格的胜率，同时加上左边一格的胜率
            res = res - dp[i + maxPts] + dp[i];
        }
        return dp[0];
    }
}
